302 - John's trip/302.2.cpp

   1 /*
   2   Problem: 302 - John's trip
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4
   5   Accepted!
   6 */
   7 using namespace std;
   8 #include <algorithm>
   9 #include <iostream>
  10 #include <iterator>
  11 #include <sstream>
  12 #include <fstream>
  13 #include <cassert>
  14 #include <climits>
  15 #include <cstdlib>
  16 #include <cstring>
  17 #include <string>
  18 #include <cstdio>
  19 #include <vector>
  20 #include <cmath>
  21 #include <queue>
  22 #include <deque>
  23 #include <stack>
  24 #include <list>
  25 #include <map>
  26 #include <set>
  27
  28 #define D(x) cout << #x " is " << x << endl
  29
  30
  31 struct edge{
  32   int to, id;
  33   edge(){}
  34   edge(int to, int id) : to(to), id(id) {}
  35   bool operator < (const edge &t) const {
  36     return id < t.id || id == t.id && to < t.to;
  37   }
  38 };
  39
  40 const int MAXN = 45, MAXE = 1995;
  41 vector<edge> g[MAXN];
  42 int degree[MAXN];
  43 bool used[MAXE];
  44 deque<int> ans;
  45
  46
  47 void dfs(int u, int last_id = -1){
  48   for (int k=0; k<g[u].size(); ++k){ //edges are sorted in increasing order of id
  49     int v = g[u][k].to, id = g[u][k].id;
  50     if (!used[id]){
  51       used[id] = true;
  52       dfs(v, id);
  53     }
  54   }
  55   ans.push_front(last_id);
  56 }
  57
  58
  59 int main(){
  60   int u, v, id;
  61   while (scanf("%d %d", &u, &v)==2 && u && v){
  62     for (int i=0; i<MAXN; ++i) g[i].clear();
  63     bzero(used, sizeof used);
  64     bzero(degree, sizeof degree);
  65     ans.clear();
  66
  67     int home = min(u, v);
  68     scanf("%d", &id);
  69     g[u].push_back(edge(v, id));
  70     g[v].push_back(edge(u, id));
  71     degree[u]++, degree[v]++;
  72
  73     while (scanf("%d %d", &u, &v)==2 && u && v){
  74       scanf("%d", &id);
  75       g[u].push_back(edge(v, id));
  76       g[v].push_back(edge(u, id));
  77       degree[u]++, degree[v]++;
  78     }
  79
  80     bool ok = true;
  81     for (int i=0; i<MAXN; ++i){
  82       sort(g[i].begin(), g[i].end());
  83       if (degree[i] % 2) { ok = false; break; }
  84     }
  85
  86     if (!ok){
  87       printf("Round trip does not exist.\n\n");
  88     }else{
  89       dfs(home);
  90       printf("%d", ans[1]);
  91       for (int i=2; i<ans.size(); ++i){
  92         printf(" %d", ans[i]);
  93       }
  94       printf("\n\n");
  95     }
  96
  97   }
  98   return 0;
  99 }